package com.atwy.sort;

/**
 * 基数排序，一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。
 * 由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。
 * <p>
 * 基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。
 * 有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。
 * 最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的。
 */
public class RadixSorting {

    public static void main(String[] args) {
        int[] array = {3, 65, 2, 34, 12, 5, 9, 12};
        sort(array);
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + "\t");
        }
        System.out.println();
        System.out.println("=============");


        int max = 800000;
        int arry[] = new int[max];
        for (int i = 0; i < max; i++) {
            arry[i] = (int)(Math.random()*8000000);
        }
        long start = System.currentTimeMillis();
        System.out.println("排序开始:"+start);
        sort(arry);
        long end = System.currentTimeMillis();
        System.out.println("排序结束:"+end);
        System.out.println("总耗时"+(end-start));
    }

    public static void sort(int[] array) {
        if (array.length < 2) {
            return;
        }
        // 1.找出最大的那个数
        int max = getMaxValue(array);

        // 2.确定最大数的位数
        //int maxDigit = (max + "").length();
        int maxDigit = getMaxLength(max);

        // 3.定义一个二维数组，表示10个桶，每个桶就是一个一维数组，因为数字范围是0-9
        int[][] bucket = new int[10][array.length];
        // 4.定义一个一维数组，用来记录bucket中每个桶里的元素个数，
        // 比如bucketElementCounts[0] = 3,说明bucket[0]，0号桶里有3个元素
        int[] bucketElementCounts = new int[10];

        // 5.循环处理，循环次数为最大数的位数
        for (int i = 0, n = 1; i < maxDigit; i++, n *= 10) {
            // 这里以个位进行解释说明，十位、百位...
            // i=0,表示取个位,用取模操作 %
            // 循环数组，取个位放入相应的桶中
            for (int j = 0; j < array.length; j++) {
                int num = array[j] / n % 10;// 个位的数是几，就放进几号桶里，
                bucket[num][bucketElementCounts[num]] = array[j];
                bucketElementCounts[num]++;
            }

            // 按个位分好桶之后，再将桶中元素按编号依次取出放回到原数组中
            int index = 0;
            for (int j = 0; j < 10; j++) {
                if (bucketElementCounts[j] > 0) {// 桶中有元素
                    for (int k = 0; k < bucketElementCounts[j]; k++) {
                        array[index++] = bucket[j][k];
                    }
                    // 桶里元素放回原数组之后，将记录桶元素个数的数组对应的置为0
                    bucketElementCounts[j] = 0;
                }
            }

        }

    }

    /**
     * 获取一个数的位数
     *
     * @param maxValue
     * @return
     */
    private static int getMaxLength(int maxValue) {
        if (maxValue == 0) {
            return 1;
        }
        int maxDigit = 0;
        while (maxValue != 0) {
            maxValue /= 10;
            maxDigit++;
        }
        return maxDigit;
    }

    /**
     * 返回数组的最大数
     *
     * @param array
     * @return
     */
    private static int getMaxValue(int[] array) {
        int max = array[0];
        for (int i = 1; i < array.length; i++) {
            if (max < array[i]) {
                max = array[i];
            }
        }
        return max;
    }
}
